package Interview.pinduoduo;

/**
 * 最小路径和(给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小
 * 输入:
 * [
 * [1,3,1],
 * [1,5,1],
 * [4,2,1]
 * ]
 * 输出: 7
 * 解释: 因为路径 1→3→1→1→1 的总和最小。
 * 动态规划
 * @author leiwenkang
 * @date 2020/4/5
 */
public class Test04最小路径和 {
    public static void main(String[] args) {
        Test04最小路径和 test04最小路径和 = new Test04最小路径和();
        int[][] matrix = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        System.out.println(test04最小路径和.findMinPathSum(matrix));
    }

    public int findMinPathSum(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return -1;
        }

        int rows = matrix.length;
        int colunms = matrix[0].length;

        int[][] dp = new int[rows][colunms];

        dp[0][0] = matrix[0][0];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < colunms; j++) {
               if (i == 0 || j == 0) {
                   if (j != 0) {
                       dp[i][j] = dp[i][j-1] + matrix[i][j];
                   } else if (i != 0) {
                       dp[i][j] = dp[i - 1][j] + matrix[i][j];
                   }
               } else {
                   //状态转移方程
                   dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
               }
            }
        }
        return dp[rows - 1][colunms - 1];
    }
}
